/*
 * @Date: 2021-09-08 09:36:08
 * @Author: Acckno1
 * @LastEditTime: 2021-09-08 09:46:21
 * @Description: 
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <utility>
using namespace std;

#define mm(a, n) memset(a, n, sizeof a)
#define mk(a, b) make_pair(a, b)

const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<LL, LL> PLL;
typedef pair<int, LL> PIL;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

const int N = 510;

int n, m;
bool g[N][N], st[N];
int d[N];

/**
 * @description: 返回经过的节点数
 * @param {int} u 需要遍历的结点
 * @return {*}
 */
int dfs(int u) {
    int cnt = 1;
    st[u] = true;
    for (int i = 1; i <= n; i ++ ) {
        if (g[u][i] && !st[i])
            cnt += dfs(i);
    }
    return cnt;
}

inline void solution() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
        d[a] ++ ; d[b] ++ ;
    }

    // an Eulerian path is a path in a graph which visits every edge exactly once.
    // Eulerian circuit is an Eulerian path which starts and ends on the same vertex.
    int cnt = dfs(1); 
    
    cout << d[1];
    for (int i = 2; i <= n; i ++ ) cout << " " << d[i];
    cout << endl;

    if (cnt == n) {
        int odd = 0;
        for (int i = 1; i <= n; i ++ ) 
            if (d[i] % 2)
                odd ++ ;
        
        if (odd == 0) printf("Eulerian\n");
        else if (odd == 2) printf("Semi-Eulerian\n");
        else printf("Non-Eulerian\n");
    } else 
        printf("Non-Eulerian\n");
}

int main() {
    freopen("input.txt", "r", stdin);
    quickread();
    solution();
    return 0;
}